public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1,2,3,3,3,3,4,5,6,7,7,7,7,8};
        search(arr,7);
    }
    public static void search(int[] arr ,int target){
        System.out.println(leftBinarySearch(arr, target));
        System.out.println(rightBinarySearch(arr, target));
    }

    public static int leftBinarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int sign = -1;

        while (left <= right) {
            int middle = (left + right) >>> 1;
            if (arr[middle] < target) {
                left = middle + 1;
            } else if (target < arr[middle]) {
                right = middle - 1;
            } else {
                sign = middle;
                right = middle - 1;
            }
        }
        return sign;
    }

    public static int rightBinarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int sign = -1;

        while (left <= right) {
            int middle = (left + right) >>> 1;
            if (arr[middle] < target) {
                left = middle + 1;
            } else if (target < arr[middle]) {
                right = middle - 1;
            } else {
                sign = middle;
                left = middle + 1;
            }

        }
        return sign;
    }

}

/*    public static void main(String[] args) {
        int[] arr = new int[]{1,4,6,9,10,18,100,118};
        System.out.println(find(arr, 5));
        System.out.println(find(arr, 10));
        System.out.println(find(arr, 1));
        System.out.println(find(arr, 118));
    }
    public static int find(int[] arr , int n){
        int left = 0;
        int right = arr.length;
        while (left < right){
            int index = (left + right) >>> 1;
            if (n < arr[index]){
                right = index;
            } else if (arr[index] < n) {
                left = index + 1;
            }else {
                return index;
            }
        }
        return -1;
    }
}*/
/*
    public static void main(String[] args) {
        int[] arr = new int[]{1,4,6,9,10,18,100,118};
        System.out.println(find(arr, 5));
        System.out.println(find(arr, 10));
        System.out.println(find(arr, 1));
        System.out.println(find(arr, 118));
    }
    public static int find(int[] arr, int n){
        int right = arr.length-1;
        int left = 0;
        while (left <= right){
            int index = (right+left) >>> 1;
            if (n < arr[index]){
                right = index - 1;
            } else if (arr[index] < n) {
                left = index + 1;
            }else {
                return index;
            }
        }
        return -1;
    }
}
*/
